package com.lihepeng.leecode.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * n 叉树的前序遍历
 */
public class PreOrderTravel {
    // 使用遍历的方式，借助stack 数据结构完成遍历
    public List<Integer> preorder(NTreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<NTreeNode> stack = new Stack<>();
        if (root == null) {
            return list;
        }
        if (root != null) {
            stack.push(root);
        }
        while (!stack.isEmpty()) {
            NTreeNode pop = stack.pop();
            list.add(pop.val);
            Collections.reverse(pop.children);
            for (NTreeNode node : pop.children) {
                stack.push(node);
            }
        }
        return list;
    }

    @Test
    public void runTest() {
        NTreeNode head = new NTreeNode(0);
        NTreeNode node1 = new NTreeNode(1);
        NTreeNode node2 = new NTreeNode(2);
        NTreeNode node3 = new NTreeNode(3);
        NTreeNode node4 = new NTreeNode(4);
        NTreeNode node5 = new NTreeNode(5);
        NTreeNode node6 = new NTreeNode(6);
        NTreeNode node7 = new NTreeNode(7);
        NTreeNode node8 = new NTreeNode(8);
        head.children.add(node1);
        head.children.add(node2);
        head.children.add(node3);
        node1.children.add(node4);
        node1.children.add(node5);
        node2.children.add(node6);
        node3.children.add(node7);
        node3.children.add(node8);

        List<Integer> preorder = preorder(head);
        System.out.println(preorder);
    }
}
